package com.teng.dataStructure.LinkedList;

/**
 * 约瑟夫环
 *
 * 构建单项环形链表的思路
 * 1、先创建第一个节点，然后first指针指向第一个节点，并形成环形
 * 2、后面当我们每次新建一个节点的时候，就把该节点加入到环形当中即可
 *
 * 遍历环形链表
 * 1、先让一个辅助变量（curboy）指向first，然后往后移动curboy
 * 2、当curboy.getNext() == first时，退出遍历
 */
public class Josephus {

    public static void main(String[] args) {
        JosephusList list = new JosephusList();
        list.addBoy(5);
        list.outBoy(2,4);
    }

}

class JosephusList {
    // 创建一个first，默认为-1表示没有编号
    private Boy first = new Boy(-1);

    // 添加小孩节点，形成环
    public void addBoy(int nums) {
        // 校验nums
        if (nums <= 1) {
            throw new RuntimeException("The Nums Must Bigger Then '1'!");
        }
        // 创建辅助变量curboy
        Boy curBoy = null;
        for (int i = 1; i <= nums; i++) {
            // 创建第一个节点
            Boy boy = new Boy(i);
            if (i == 1) {
                // 赋值first
                first = boy;
                // 形成环
                first.setNext(boy);
                boy.setNext(first);
                curBoy = boy; // 赋值变量
            } else {
                /*
                  因为curBoy始终指向最新加入的节点，所以添加的时候只需要将节点添加至curBoy.setNext()即可
                  然后将添加进来的节点指向first形成闭环
                  最后重新赋值curBoy，使其重新指向最新的节点
                 */
                curBoy.setNext(boy);
                boy.setNext(first);
                curBoy = boy; // 不是很懂
            }
        }
    }

    // 遍历
    public void list() {
        if (first == null) {
            System.out.println("无法遍历空链表");
            return;
        }
        /*
          创建变量curBoy
          原因：first不能动，必须一直指向第一个节点，因为要借助curBoy.getNext() != first这个条件退出循环
         */
        Boy curBoy = first;
        while (curBoy.getNext() != first) {
            System.out.println(curBoy);
            curBoy = curBoy.getNext();
        }
        System.out.println(curBoy);

        while (curBoy.getNext() != first) {
            System.out.println(curBoy);
            curBoy = curBoy.getNext();
        }
    }

    // 节点出圈
    public void outBoy(int startNo, int k) {
        /*
        不玩的情况
        1：开始报数的点小于2
        2：报数的次数大于等于2
         */
        if (first == null || startNo < 1 || k < 2) {
            throw new RuntimeException("Please Check Your Params!");
        }
        // 创建辅助指针
        Boy helpBoy = first;
        // 将helpBoy指向最后一个节点
        while (helpBoy.getNext() != first) {
            helpBoy = helpBoy.getNext();
        }
        // 定位开始节点
        while (startNo != first.getNo()) {
            first = first.getNext();
            helpBoy = helpBoy.getNext();
        }
        // 开始
        int count = 1; // 计数
        while (true) {
            // 设置结束规则：圈中只剩下一个小孩，因为是环形链表，即first = first.getNext()表示圈中只剩下一个节点
            if (first == first.getNext()) {
                break;
            }
            int no = 0; // 1、获取出圈小孩的编号(将first设置为数完first的前一个节点)
            for (int i = 1; i <= k-2; i++) {
                no = first.getNext().getNo();
                first = first.getNext();
            }
            System.out.println("第" + count + "次报数出圈的小孩编号为：" + first.getNext().getNo());
            /*
            2、将小孩出圈，即移动first和helpBoy
            1) 先将first 赋值给 helpBoy
            2) first后移2次
            3) 再将helpBoy.setNext() 设置为first
             */
            helpBoy = first;
            first = first.getNext().getNext();
            helpBoy.setNext(first);
            count++;
        }
        System.out.println("最后留下的小孩为：" + first.getNo());
    }
}

// 创建一个boy类，表示一个节点
class Boy{
    private int no; // 编号
    private Boy next; // 指向下一节点，默认为null

    public Boy() {
    }

    public Boy(int no) {
        this.no = no;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public Boy getNext() {
        return next;
    }

    public void setNext(Boy next) {
        this.next = next;
    }

    @Override
    public String toString() {
        return "现在为您输出的是第”" + no + "”个节点";
    }
}
